package com.chj.jz.dp.class06;

public class Code09_OnesAndZeroes {
	/**
	 * @param strs:
	 *            an array with strings include only 0 and 1
	 * @param m:
	 *            An integer
	 * @param n:
	 *            An integer
	 * @return: find the maximum number of strings
	 */
	public static int findMaxForm(String[] A, int m, int n) {
		if (A.length == 0) {
			return 0;
		}

		int T = A.length;
		int i, j, k, a0, a1;
		int old , now = 0;

		int[][][] f = new int[2][m + 1][n + 1];
		for (j = 0; j <= m; j++) {
			for (k = 0; k <= n; k++) {
				f[now][j][k] = 0;
			}
		}

		// int res = 0;
		for (i = 1; i <= T; ++i) {

			old = now;
			now = 1 - now;
			
			a0 = a1 = 0;
			for (j = 0; j < A[i - 1].length(); j++) {
				if (A[i - 1].charAt(j) == '0') {
					a0++;
				} else {
					a1++;
				}
			}

			for (j = 0; j <= m; ++j) {
				for (k = 0; k <= n; ++k) {
					// do not take A[i - 1]
					f[now][j][k] = f[old][j][k];

					// take A[i - 1]
					if (j >= a0 && k >= a1) {
						f[now][j][k] = Math.max(f[now][j][k], f[old][j - a0][k - a1] + 1);
					}
				}
			}
		}

		return f[now][m][n];
	}
	
	 public static void main(String[] args) {
			{
				String[] arrK = new String[] {"10", "0001", "111001", "1", "0"};
				int m = 5;
				int n = 3;
				System.out.println(findMaxForm(arrK, m, n));
			}
			{
				String[] arrK = new String[] {"10", "0001", "111001", "1", "0"};
				int m = 7;
				int n = 7;
				System.out.println(findMaxForm(arrK, m, n));
			}
	    }
}
